package lyl.sort;

public class QuickEx {

    public void quickSort(int[] arr, int start , int end){
        if(start >= end){
            return;
        }
        int left = start;
        int right = end;
        int pivot = arr[(start + end ) / 2];//任意值
        while(left <= right){
            while (left <= right && arr[left]<pivot){
                left ++;
            }
            while (left <=right && arr[right]>pivot){
                right --;
            }
            if(left<=right){
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
                left ++;
                right --;
            }
        }
        quickSort(arr,start,right);
        quickSort(arr,left,end);
    }

    //查nums中第k大的
    public int findKthLargest(int[] nums , int k){
        if(nums == null || nums.length == 0|| k <= 0 ||k > nums.length){
            return -1;
        }

        return partition(nums,0,nums.length - 1,nums.length - k);
    }

    private int partition(int[] nums, int start, int end, int k) {

        if(start >= end){
            return nums[k];
        }
        int left = start;
        int right = end;
        int pivot = nums[(start + end ) / 2];
        while(left <= right){
            while (left <= right && nums[left]<pivot){
                left ++;
            }
            while (left <=right && nums[right]>pivot){
                right --;
            }
            if(left<=right){
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left ++;
                right --;
            }
        }
        //在左边
        if(k <= right){
            return partition(nums,start,right,k);
        }
        //在右边
        if(k >= left){
            return partition(nums,left,end,k);
        }
        return nums[k];
    }
}
